Date: Wed, 08 Jan 1997 20:38:01 GMT
Server: NCSA/1.4.2
Content-type: text/html

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>CSE 322  
Assignment 8 Solution Set  
Wednesday, February 28, 1996</TITLE>
</HEAD>
<BODY>
<meta name="description" value="CSE 322  
Assignment 8 Solution Set  
Wednesday, February 28, 1996">
<meta name="keywords" value="hw8soln">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
 <BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A>   <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif">   <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif">         <BR>
<B> Next:</B> <A NAME=tex2html2 HREF="node1.html">   About this document </A>
<BR> <HR> <P>
<P>
<H1>CSE 322  
Assignment 8 Solution Set  
Wednesday, February 28, 1996</H1>
<P><STRONG></STRONG><P>
<P><STRONG></STRONG><P>
<P>
<OL><LI> 
Consider the NFA <IMG  ALIGN=MIDDLE ALT="" SRC="img1.gif"> 
where <IMG  ALIGN=BOTTOM ALT="" SRC="img2.gif"> is given by the table:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img3.gif"><P>
<P>
We can construct a DFA <IMG  ALIGN=MIDDLE ALT="" SRC="img4.gif"> where 
<IMG  ALIGN=MIDDLE ALT="" SRC="img5.gif"> is given by the table (using the subset construction):
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img6.gif"><P>
<P>
and where 
<IMG  ALIGN=MIDDLE ALT="" SRC="img7.gif"> 
and
<IMG  ALIGN=MIDDLE ALT="" SRC="img8.gif">.
<P>
<LI> 
Below are the steps for converting the NFA of problem 1 into a regular
expression. We start with the original NFA:
<br>
<center>
<IMG ALIGN=MIDDLE SRC="hw8dfao.gif">
</center>
<P>
First, we make a new start state that has no incoming arcs:
<br>
<center>
<IMG ALIGN=MIDDLE SRC="hw8dfas.gif">
</center>
<p>
Next, make a new final state with no outgoing arcs:
<br>
<center>
<IMG ALIGN=MIDDLE SRC="hw8dfaf.gif">
</center>
<P>
Eliminate a state.  The state <IMG  ALIGN=MIDDLE ALT="" SRC="img9.gif"> looks like a good candidate:
<br>
<center>
<IMG ALIGN=MIDDLE SRC="hw8dfaq0.gif">
</center>
<p>
Eliminate state <IMG  ALIGN=MIDDLE ALT="" SRC="img10.gif">:
<br>
<center>
<IMG ALIGN=MIDDLE SRC="hw8dfaq2.gif">
</center>
<p>
Eliminate <IMG  ALIGN=MIDDLE ALT="" SRC="img11.gif">:
<br>
<center>
<IMG ALIGN=MIDDLE SRC="hw8dfaq1.gif">
</center>
<p>
Accounting for the final start state, the equivalent regular expression is
<IMG  ALIGN=MIDDLE ALT="" SRC="img12.gif">. This can be simplified to
<IMG  ALIGN=MIDDLE ALT="" SRC="img13.gif">.
<LI> 
<b> Proof that that regular languages are closed under reversal:</b>
Suppose the language <b>L</b> over <IMG  ALIGN=BOTTOM ALT="" SRC="img14.gif"> is regular.  
It must be accepted by some NFA 
<IMG  ALIGN=MIDDLE ALT="" SRC="img15.gif">.  
Consider the NFA <IMG  ALIGN=MIDDLE ALT="" SRC="img16.gif"> where
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img17.gif"><P>
<P>
We will show that <IMG  ALIGN=BOTTOM ALT="" SRC="img18.gif"> accepts <IMG  ALIGN=BOTTOM ALT="" SRC="img19.gif"> with the following behavioral lemma:
<P>
<b> Behavioral Lemma:</b> For all <IMG  ALIGN=MIDDLE ALT="" SRC="img20.gif">, <IMG  ALIGN=MIDDLE ALT="" SRC="img21.gif">
<IMG  ALIGN=MIDDLE ALT="" SRC="img22.gif"> if and only if 
<IMG  ALIGN=MIDDLE ALT="" SRC="img23.gif">.
<P>
Given that this lemma is true, we can prove that <IMG  ALIGN=MIDDLE ALT="" SRC="img24.gif">.
Suppose <IMG  ALIGN=MIDDLE ALT="" SRC="img25.gif"> and <IMG  ALIGN=MIDDLE ALT="" SRC="img26.gif">.  Let <b>x = ay</b> for <IMG  ALIGN=MIDDLE ALT="" SRC="img27.gif">
and <IMG  ALIGN=MIDDLE ALT="" SRC="img28.gif">.  Note that <IMG  ALIGN=MIDDLE ALT="" SRC="img29.gif">.  It follows that:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img30.gif"><P>
<P>
Suppose that <IMG  ALIGN=MIDDLE ALT="" SRC="img31.gif"> and <IMG  ALIGN=MIDDLE ALT="" SRC="img32.gif">.  Again, let <b>x=ay</b>:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img33.gif"><P>
<P>
Consider when <IMG  ALIGN=BOTTOM ALT="" SRC="img34.gif">:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img35.gif"><P>
<P>
Combining these observations, we have <IMG  ALIGN=MIDDLE ALT="" SRC="img36.gif">, and so 
there is an NFA that accepts <IMG  ALIGN=BOTTOM ALT="" SRC="img37.gif">.
Thus, if <b>L</b> is regular, <IMG  ALIGN=BOTTOM ALT="" SRC="img38.gif"> is regular.
</OL><BR> <HR>
<UL> 
<LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000">   About this document ... </A>
</UL>
<BR> <HR>
<P><ADDRESS>
<I>James Fix <BR>
Wed Feb 28 11:09:35 PST 1996</I>
</ADDRESS>
</BODY>
